home *** CD-ROM | disk | FTP | other *** search
/ Australian Personal Computer 1999 September / Sept 99, disk1=APC491.iso / workshop / c / sort1.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1999-06-04  |  3.0 KB  |  147 lines
  1. // **************************************************************
  2. // sort1.cpp
  3. // Example program for Simple C++
  4. //
  5. // (c) 1999 Emmenjay Consulting Pty Ltd                          
  6. //                                                               
  7. // History                                                       
  8. // 04/06/99 MJS  Initial Coding.                                 
  9. //                                                               
  10. // **************************************************************
  11.  
  12. #include <iostream>
  13. #include <cstring>
  14.  
  15.  
  16. void DeleteData( char ** &data, int NumLines );
  17.  
  18. // ALLOCATE A NEW DATA ARRAY, FREEING THE
  19. // OLD ONE
  20. int Expand( char ** &data, int &siz, 
  21.             int newsiz )
  22. {
  23.   char **newdat = new char * [newsiz];
  24.   int i;
  25.  
  26.   if (newdat==NULL) {
  27.     // ALLOCATION FAILED
  28.     return 0;
  29.   }
  30.  
  31.   if (siz>0) {
  32.     // COPY THE OLD DATA TO THE NEW
  33.     for (i=0; i<siz; i++)
  34.       newdat[i] = data[i];
  35.     // DELETE THE OLD DATA
  36.     delete [] data;
  37.   }
  38.  
  39.   // SET NEW (UNINITIALISED)
  40.   // POINTERS TO NULL
  41.   for (i=siz; i<newsiz; i++)
  42.     newdat[i] = NULL;
  43.  
  44.   // SET VALUES TO RETURN
  45.   data = newdat;
  46.   siz = newsiz;
  47.  
  48.   return 1;
  49. }
  50.  
  51. // MAKE A DUPLICATE OF A STRING
  52. char *DupStr( char *str )
  53. {
  54.   char *newstr = 
  55.     new char [strlen(str)+1];
  56.  
  57.   if (newstr)
  58.     strcpy( newstr, str );
  59.  
  60.   return newstr;
  61. }
  62.  
  63. int ReadData( char ** &data )
  64. {
  65.   const int LINELEN = 256;
  66.   int NumLines = 0;
  67.   int MaxLines = 0;
  68.   char buffer[LINELEN];
  69.  
  70.   Expand( data, MaxLines, 100 );
  71.  
  72.   while (!std::cin.eof()) {
  73.     std::cin.getline( buffer, LINELEN );
  74.     if (NumLines==MaxLines) { 
  75.       // OUT OF POINTERS, ALLOCATE SOME MORE
  76.       if (!Expand(data, MaxLines, MaxLines*2)) {
  77.         DeleteData( data, NumLines );
  78.         return 0;
  79.       }
  80.     }
  81.     // COPY THE STRING 
  82.     data[NumLines] = DupStr( buffer );
  83.     if (data[NumLines]==NULL) {
  84.       // COPY FAILED (NO MEMORY)
  85.       DeleteData( data, NumLines );
  86.       return 0;
  87.     }
  88.     NumLines++;
  89.   }
  90.  
  91.   return NumLines;
  92. }
  93.  
  94. // STANDARD INSERTION SORT
  95. // ADAPTED FROM SEDGEWICK'S
  96. // ALGORITHMS IN C++
  97. void SortData( char **data, int NumLines )
  98. {
  99.   for (int i=1; i<NumLines; i++) {
  100.     char *tmp;
  101.     int j;
  102.  
  103.     tmp = data[i];
  104.     j = i;
  105.     while (j>0 && strcmp(data[j-1],tmp)>0) {
  106.       data[j] = data[j-1];
  107.       j--;
  108.     }
  109.     data[j] = tmp;
  110.   }
  111. }
  112.  
  113. void WriteData( char **data, int NumLines )
  114. {
  115.   for (int i=0; i<NumLines; i++)
  116.     std::cout << data[i] << '\n';
  117. }
  118.  
  119. void DeleteData( char ** &data, int NumLines )
  120. {
  121.   if (data) {
  122.     // ARRAY OF POINTERS IS VALID
  123.     for (int i=0; i<NumLines; i++)
  124.       // DELETE EACH VALID STRING
  125.       if (data[i])
  126.         delete data[i];
  127.     // DELETE ARRAY OF POINTERS
  128.     delete [] data;
  129.     data = NULL;
  130.   }
  131. }
  132.  
  133. int main( void )
  134. {
  135.   char **data;
  136.   int NumLines;
  137.  
  138.   NumLines = ReadData( data );
  139.   if (!NumLines)
  140.     return 1;
  141.   SortData( data, NumLines );
  142.   WriteData( data, NumLines );
  143.   DeleteData( data, NumLines );
  144.  
  145.   return 0;
  146. }
  147.